package me.mingshan.leetcode;

/**
 * https://leetcode.cn/problems/merge-in-between-linked-lists/description/
 * <p>
 * 给你两个链表 list1 和 list2 ，它们包含的元素分别为 n 个和 m 个。
 * <p>
 * 请你将 list1 中下标从 a 到 b 的全部节点都删除，并将list2 接在被删除节点的位置。
 * <p>
 * 下图中蓝色边和节点展示了操作后的结果：
 * <p>
 * <p>
 * 请你返回结果链表的头指针。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * <p>
 * 输入：list1 = [10,1,13,6,9,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
 * 输出：[10,1,13,1000000,1000001,1000002,5]
 * 解释：我们删除 list1 中下标为 3 和 4 的两个节点，并将 list2 接在该位置。上图中蓝色的边和节点为答案链表。
 * 示例 2：
 * <p>
 * <p>
 * 输入：list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004]
 * 输出：[0,1,1000000,1000001,1000002,1000003,1000004,6]
 * 解释：上图中蓝色的边和节点为答案链表。
 * <p>
 * <p>
 * 1 <= a <= b < list1.length - 1
 *
 * @author hanjuntao
 * @date 2025/7/31 0031
 */
public class L_1669_merge_in_between_linked_lists {

    public static void main(String[] args) {
        ListNode list1 = new ListNode(10);
        list1.next = new ListNode(1);
        list1.next.next = new ListNode(13);
        list1.next.next.next = new ListNode(6);
        list1.next.next.next.next = new ListNode(9);
        list1.next.next.next.next.next = new ListNode(5);
        ListNode list2 = new ListNode(1000000);
        list2.next = new ListNode(1000001);
        list2.next.next = new ListNode(1000002);
        ListNode result = mergeInBetween(list1, 3, 4, list2);

        ListNode.print(result); // [10,1,13,1000000,1000001,1000002,5]
    }

    /**
     * 由题可知：1 <= a <= b < list1.length - 1
     * <p>
     * 说明a和b就在list1的中间， 不会出现在头节点和尾节点
     *
     * 思路：
     *
     * 1. 获取list2的头节点和尾节点
     * 2. 遍历list1，找到a位置的前一个节点pre1；找到b位置的下一个节点next1
     * 3. 将pre1的next指针指向list2的头节点
     * 4. 将list2的尾节点的next指针指向next1
     *
     * @param list1
     * @param a
     * @param b
     * @param list2
     * @return
     */
    public static ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
        // 获取list2的头节点，尾节点
        ListNode head2 = list2;
        ListNode tail2 = null;

        ListNode curr2 = list2;

        while (curr2 != null) {
            if (curr2.next == null) {
                tail2 = curr2;
                break;
            }
            curr2 = curr2.next;
        }

        ListNode curr1 = list1;
        int index1 = 0;
        ListNode pre1 = null;

        // 第a的节点的前一个节点
        ListNode pre1A = null;

        // 第b的节点的前一个节点
        ListNode next1B = null;

        while (curr1 != null) {
            // 找到第a个节点
            if (index1 == a) {
                pre1A = pre1;
            }

            // 找到第b个节点, 断开连接
            if (index1 == b) {
                next1B = curr1.next;
                curr1.next = null;
                break;
            }

            index1++;
            pre1 = curr1;
            curr1 = curr1.next;
        }

        // list1 接上list2的头
        pre1A.next = head2;
        // list2的尾 接上list1的剩余部分
        tail2.next = next1B;

        return list1;
    }
}
